One very important use of binary trees is to store arithmetical expressions (and other kinds of expressions). We always think of expressions as looking like this 14*X^2 + 7*X + 2 or like this 75.3 * ((-37+63/4)^2). (Note that the uparrow ^ means "raised to the power of.") However, this is sometimes an inconvenient way of storing an expression. When compiling a program, for example, a computer will often take the expression and put each number, variable, or operator (+,-,*,/,^) into its own node in a more convenient data structure, such as a binary tree. This action of breaking up the expression into parts is called "parsing."
In the typical parse tree, each operator is put into its own node, and the two numbers or variables it operates on (called the "operands") become its children.
Often the operands are not actual numbers or variables, but results of other calculations; for example, in (4+2) * (7+6), the left child of the times sign * is the sub-expression (4+2), while the right child is (7+6). In this example's parse tree, * would be the root, its children would be + and +, and their children would be 4 and 2, and 7 and 6, respectively. You can try this out with the command Parse an Infix Expression to have the Macintosh parse your own expressions.
To find the numerical value of a parse tree, start from the bottom and move up. Each time you come to an operator, do the operation and put the answer where the operator is. In the example (4+2) * (7+6), you first replace the + and + by 6 and 13, respectively, and then replace the * by 78.
We call the convention of writing the operator between the operands "infix." There are other notations; for example, Hewlett-Packard calculators use "postfix" notation, in which you enter both operands and THEN the operator. Instead of writing 8 / 7, in postfix notation you write 8 7 / . To write 8 / (3+4) instead, you replace the 7 by 3 4 +, leaving you the hard-to-read 8 3 4 + /. Yet another kind of notation is "prefix," where the operator preceeds the operands, as in / 8 7.
Prefix and postfix notation are very hard to read, but they have an interesting advantage over infix: you never need parentheses. With infix notation, there are situations in which you are forced to use parentheses, whether or not you use the operator precedence convention.
The rules for infix notation are as follows. First, observe any parentheses. Second, observe "precedence," which means do exponents first, then multiply and divide, and lastly add and subtract. Therefore, 2+4*8^6 is the same as 2+ (4 * (8^6)). Third, when all else is equal, perform operations from left to right, so that 8-4-3 is really (8-4) -3 and not 8- (4-3). This complicated set of rules for reading infix expressions is one reason that computers would rather store the expression in a parse tree.
Try typing in some of your own expressions for the Mac to parse, and then Explain Traversals to find out more about parse trees. (Note that in postfix and infix you need to put spaces between operands to separate them.)